package xyz.sekai52799.answer.a2201_a2400;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Question2368 {
//    现有一棵由 n 个节点组成的无向树，节点编号从 0 到 n - 1 ，共有 n - 1 条边。
//
//    给你一个二维整数数组 edges ，长度为 n - 1 ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条边。另给你一个整数数组 restricted 表示 受限 节点。
//
//    在不访问受限节点的前提下，返回你可以从节点 0 到达的 最多 节点数目。
//
//    注意，节点 0 不 会标记为受限节点。

    private int ans = 0;
    public int reachableNodes(int n, int[][] edges, int[] restricted) {
        Set<Integer> restrictedSet = new HashSet<>();
        for (int r : restricted){
            restrictedSet.add(r);
        }

        List<Integer>[] edgeList = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            edgeList[i] = new ArrayList<Integer>();
        }

        for (int[] line : edges){
            if (!restrictedSet.contains(line[0]) && !restrictedSet.contains(line[1])){
                edgeList[line[0]].add(line[1]);
                edgeList[line[1]].add(line[0]);
            }
        }

        dfs(0, -1, edgeList);

        return ans;
    }

    private void dfs(int x, int fa, List<Integer>[] line){
        ans++;
        for (int i : line[x]){
            if (i != fa){
                dfs(i, x, line);
            }
        }
    }
}
